import java.util.PriorityQueue;

public class Top_k {
    //找出数组中前k个最小的元素；
    //方法：
    //假设k=3;
    //1.将数组中前3个元素进行堆排序。堆排序为大根堆；
    //2.进行将数组中其他元素进行依次与堆排序中堆顶元素比较，
    // 若堆顶元素大于比较的元素就将堆顶元素删除，放入要比较的元素；依次进行直到数组中元素比较完毕；
    //3.最后将堆中三个最小的元素放入可以存放3个元素的数组中；
    public int[] smallestK(int[] arr,int k){
        int[] ret=new int[k];
        if(arr==null||k==0){
            return ret;
        }
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(k,new IntCmp());
        for(int i=0;i<k;i++){
            priorityQueue.offer(arr[i]);
        }
        for(int i=k;i< arr.length;i++){
            int peek= priorityQueue.peek();
            if(arr[i]<peek){
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        for(int i=0;i<k;i++){
            ret[i]= priorityQueue.poll();
        }
        return ret;
    }
    //方法二；
    //直接进行优先级队列堆排序；
    //将堆排中前k个元素进行放入数组；
    public int[] smallestK1(int[] arr ,int k){
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(k,new IntCmp());
        for(int i=0;i< arr.length;i++){
            priorityQueue.offer(arr[i]);
        }
        int[] ret=new int[k];
        for(int i=0;i<k;i++){
            ret[i]= priorityQueue.poll();
        }
        return ret;
    }

}
